#include "../include/sort.h"

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

#define LCHILD(x) ((2*x)+1)
#define RCHILD(x) ((2*x)+2)

int FindInsertPos( ElemType *es, int length, ElemType e )
{
    int offset = 0;

    while ( es[offset] <= e && offset < length ) {
        ++offset;
    }

    return offset;
}

void InsertSort( ElemType *es, int length )
{
    int count = 1;
    int offset = 0;
    int end = 0;

    ElemType e;

    for ( count = 1; count < length; ++count ) {
        end = count;
        offset = FindInsertPos( es, end, es[end] );

        e = es[end];

        while ( end > offset ) {
            es[end] = es[end - 1];
            --end;
        }

        es[offset] = e;
    }
}

BOOL VectorEqual( ElemType *es1, ElemType *es2, int length )
{
    int count = 0;
    BOOL equal = TRUE;

    while ( count < length ) {
        if ( es1[count] != es2[count] ) {
            equal = FALSE;
            break;
        }

        ++count;
    }

    return equal;
}

void SelectSort( ElemType *es, int length )
{
    int count = 0;
    int offset = 0;
    int minoffset = 0;

    for ( ; count < length - 1; ++count ) {
        for ( offset = count, minoffset = count; offset < length; ++offset ) {
            if ( es[offset] < es[minoffset] ) {
                minoffset = offset;
            }
        }

        swap( &es[count], &es[minoffset] );
    }
}

void swap( ElemType *e1, ElemType *e2 )
{
    ElemType e = *e1;
    *e1 = *e2;
    *e2 = e;
}

void BubbleSort( ElemType *es, int length )
{
    int cur = 0;
    int next = 0;
    BOOL flag = TRUE;

    for ( cur = 1; cur < length; ++cur ) {
        if ( !flag ) {
            break;
        }

        flag = FALSE;

        for ( next = 0; next < length - cur; ++next ) {
            if ( es[next] > es[next + 1] ) {
                swap( &es[next], &es[next + 1] );
                flag = TRUE;
            }
        }
    }

}

void QuickSortInner( ElemType *es, int _low, int _high )
{
    int low = _low;
    int high = _high;

    if ( high > low ) {
        while ( high > low ) {
            while ( es[high] >= es[low] && high > low ) {
                --high;
            }

            if ( high > low ) {
                swap( &es[high], &es[low] );
                ++low;
            }


            while ( es[low] <= es[high] && high > low ) {
                ++low;
            }

            if ( high > low ) {
                swap( &es[high], &es[low] );
                --high;
            }
        }

        QuickSortInner( es, _low, low - 1 );
        QuickSortInner( es, low + 1, _high );
    }
}

void QuickSort( ElemType *es, int length )
{
    QuickSortInner( es, 0, length - 1 );
}

void AdjustHeap( ElemType *es, int root, int length )
{
    int left = LCHILD( root );
    int right = RCHILD( root );

    int maxpos = root;

    while ( left < length || right < length ) {
        if ( left < length && es[left] > es[maxpos] ) {
            maxpos = left;
        }

        if ( right < length && es[right] > es[maxpos] ) {
            maxpos = right;
        }

        if ( root != maxpos ) {
            swap( &es[root], &es[maxpos] );

            root = maxpos;
            left = LCHILD( root );
            right = RCHILD( root );
        } else {
            break;
        }
    }
}

void BuildMixHeap( ElemType *es, int length )
{
    int offset = length / 2 - 1;

    for ( ; offset >= 0; --offset ) {
        AdjustHeap( es, offset, length );
    }
}


void HeapSort( ElemType *es, int length )
{
    int count = 1;
    BuildMixHeap( es, length );

    for ( ; count < length; ++count ) {
        swap( &es[length - count], &es[0] );
        AdjustHeap( es, 0, length - count );
    }
}

void Print( ElemType *es, int length )
{
    int offset = 1;

    if ( es == NULL || length <= 0 ) {
        return;
    }

    printf( "[%d", es[0] );

    while ( offset < length ) {
        printf( ", %d", es[offset] );
    }

    printf( "]\n" );
}

void Merge( ElemType *es1, ElemType *es2,
            int length1, int length2,
            ElemType *esout )
{
    int vec1count = 0;
    int vec2count = 0;
    int outcount = 0;

    while ( vec1count < length1 && vec2count < length2 ) {
        if ( es1[vec1count] < es2[vec2count] ) {
            esout[outcount] = es1[vec1count];
        } else {
            esout[outcount] = es2[vec2count];
        }
    }

    if ( vec1count < length1 ) {
        memcpy( &esout[outcount], &es1[vec1count],
                sizeof( ElemType ) * length1 - vec1count );
        return;
    }

    if ( vec2count < length2 ) {
        memcpy( &esout[outcount], &es1[vec1count],
                sizeof( ElemType ) * length1 - vec1count );
        return;
    }
}

void MergeSort( ElemType *es, int length )
{
    int count = 0;
    int grouplength = 2;

    ElemType *esTemp = ( ElemType * )malloc( sizeof( ElemType ) * length );

    while ( count < grouplength ) {

    }
}
